package _array.sort

import org.junit.Assert
import org.junit.Test

/**
 * https://www.runoob.com/w3cnote/insertion-sort.html
 * 插入排序
 */
class InsertionSortTest {
    @Test
    fun test1() {
        val nums = intArrayOf(15, 5, 30, 90, 50)
        insertionSort(nums) // -1
        val expect = intArrayOf(5, 15, 30, 50, 90)
        Assert.assertEquals(expect.contentToString(), nums.contentToString())
    }

    @Test
    fun test2() {
        val nums = intArrayOf(15)
        insertionSort(nums) // -1
        val expect = intArrayOf(15)
        Assert.assertEquals(expect.contentToString(), nums.contentToString())
    }

    @Test
    fun test3() {
        val nums = intArrayOf(30, 40)
        insertionSort(nums) // -1
        val expect = intArrayOf(30, 40)
        Assert.assertEquals(expect.contentToString(), nums.contentToString())
    }


    @Test
    fun test4() {
        val nums = intArrayOf(40, 30, 20)
        insertionSort(nums) // -1
        val expect = intArrayOf(20, 30, 40)
        Assert.assertEquals(expect.contentToString(), nums.contentToString())
    }

    /**
     * https://www.runoob.com/w3cnote/insertion-sort.html
     * 插入排序
     *
     * 平均时间复杂度：O(N x N)
     * 最好时间复杂度：O(N)
     * 最坏时间复杂度：O(N x N)
     *
     * 空间复杂度：O（1）
     */
    private fun insertionSort(nums: IntArray) {
        if (nums.size <= 1) {
            return
        }
        var sortedEnd: Int = 0
        var toSortIndex: Int = 1
        var temp: Int

        while (sortedEnd < nums.size - 1) { // [sortedEnd,endIndex)
            for (i in 0..sortedEnd) { // [0,sortedEnd]
                if (nums[toSortIndex] <= nums[i]) {
                    temp = nums[i]
                    nums[i] = nums[toSortIndex]
                    nums[toSortIndex] = temp
                }
            }
            toSortIndex++
            sortedEnd++
        }
    }
}